package cn.leonis.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Tobi
 * @Date 2021-07-23 下午6:22
 * 三数之和
 */
public class ThreeSumSolution {

    public static void main(String[] args) {

    }

    /**
     * 解法一：暴力解法，三重循环 O(n * n * n)，超出时间限制
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length <= 2) {
            return result;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> tempList = Arrays.asList(Integer.valueOf(nums[i]), Integer.valueOf(nums[j]), Integer.valueOf(nums[k]));
                        if (!result.contains(tempList)) {
                            result.add(tempList);
                        }
                    }
                }
            }
        }

        return result;

    }

    /**
     * 解法二，排序+双指针
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum1(int[] nums) {

        int length = nums.length;

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || length <= 2) {
            return result;
        }

        Arrays.sort(nums);

        for (int first = 0; first < length; ++first) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = length - 1;
            int target = -nums[first];
            for (int second = first + 1; second < length; ++second) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[first]);
                    tempList.add(nums[second]);
                    tempList.add(nums[third]);
                    result.add(tempList);
                }
            }
        }


        return result;

    }

}
